package com.leetcode.partition8;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/11/11 11:52
 */
public class LC752打开转盘锁 {

    public static int openLock(String[] deadends, String target) {
        Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
        if ("0000".equals(target)) return 0;
        if (deadSet.contains(target) || deadSet.contains("0000")) return -1;
        return bfs(target, deadSet);
    }

    public static void main(String[] args) {
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        System.out.println(openLock(deadends, target));
    }

    private static int bfs(String target, Set<String> deadSet) {
        LinkedList<String> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        Map<String, Integer> dis1 = new HashMap<>(), dis2 = new HashMap<>();
        queue1.addLast("0000");
        dis1.put("0000", 0);
        queue2.addLast(target);
        dis2.put(target, 0);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            int ans = queue1.size() <= queue2.size() ? search(queue1, dis1, dis2, deadSet)
                    : search(queue2, dis2, dis1, deadSet);
            if (ans != -1) return ans;
        }
        return -1;
    }

    private static int search(LinkedList<String> queue, Map<String, Integer> dis, Map<String, Integer> opposite
            , Set<String> deadSet) {
        String s = queue.pollFirst();
        int step = dis.get(s);
        //遍历每一个字符
        for (int i = 0; i < s.length(); i++) {
            //对当前位进行替换，j只能取1和-1，1表示正着转，-1表示反着转
            for (int j = -1; j <= 1; j += 2) {
                int nextNum = (s.charAt(i) - '0' + j) % 10;
                if (nextNum == -1) nextNum = 9;
                String next = s.substring(0, i) + nextNum + s.substring(i + 1);
                //在当前路径上不能重复，且不能出现在锁定里面
                if (deadSet.contains(next) || dis.containsKey(next)) continue;
                //在另一个方向出现过，直接返回总距离
                if (opposite.containsKey(next)) {
                    return step + 1 + opposite.get(next);
                }
                dis.put(next, step + 1);
                queue.addLast(next);
            }
        }
        return -1;
    }
}
